package leetcode.editor.cn;

public class _31_NextPermutation {
    public static void main(String[] args) {
        Solution solution = new _31_NextPermutation().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private void swap(int[] nums, int i, int j) {
            int temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
        }

        public void nextPermutation(int[] nums) {
            int n = nums.length;
            int i = n - 2, j = n - 1, k = n - 1;

            // nums[i] 为要交换的较小数
            while (i >= 0 && nums[i] >= nums[j]) {
                i--;
                j--;
            }

            // 如果 i = -1 说明当前是降序，此时字典序最大
            if (i >= 0) {
                // nums[k] 为要交换的较大数
                while (nums[i] >= nums[k]) {
                    k--;
                }
                swap(nums, i, k);
            }

            // reverse [j, r]，降序变升序
            int r = n - 1;
            while (j < r) {
                swap(nums, j, r);
                j++;
                r--;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}